CF575A Fibonotci

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵,可以暴力计算。

我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。

因为有散段所以考虑用线段树维护区间矩阵的乘法,整段直接矩阵快速幂

但要注意修改操作相邻时影响的矩阵会重复,可以存进 vector 里暴力修改后一起乘。

代码大部分是考场写的,太丑就不放了。虽然口胡很简单但是写起来是真的恶心。